#include <bits/stdc++.h>
using namespace std;
const int N(2e5 + 5);
int a[N];
array<int, 2005> dp[2005];//dp[i][2001] = max1, dp[i][2002] = max2
inline int ck(int x, int y) {
    return dp[x][y] == dp[x][2001] ? dp[x][2002] : dp[x][2001];
}
inline void updmax(int x, int y, int v) {
    dp[x][y] = v;
    if (v >= dp[x][2001]) dp[x][2002] = dp[x][2001], dp[x][2001] = v;
    else if (v > dp[x][2002]) dp[x][2002] = v;
}
void work() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    /*
    if (n <= 0) {
        int up(1 << n), ans = 0;
        for (int i = 0; i < up; i++) {
            int tt = 0;
            bitset<20> b = i; int la = -1, lb = -1;
            for (int j = 0; j < n; j++) {
                if (b[j]) {
                    if (la != -1 && a[la] == a[j]) tt += a[j];
                    la = j;
                } else {
                    if (lb != -1 && a[lb] == a[j]) tt += a[j];
                    lb = j;
                }
            }
            ans = max(ans, tt);
        }
        cout << ans << '\n';
        return;
    }
    */
    if (n <= 2000) {
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1];
            for (int j = 1; j <= 2000; j++) if (dp[i][j] != -1 && a[i] == a[i - 1]) {
                updmax(i, j, dp[i][j] + a[i]);
            }
            int lst = -1, res = 0;
            for (int j = i - 2; ~j; j--) {
                if (a[j + 1] == lst) res += a[j + 1];
                int ma = 0;
                if (dp[j][a[j + 1]] != -1) ma = dp[j][a[j + 1]] + a[j + 1];
                ma = max(ma, ck(j, a[j + 1]));
                updmax(i, a[i - 1], max(dp[i][a[i - 1]], ma + res + (a[i] == a[j]) * a[i]));
                lst = a[j + 1];
            }
        }
        cout << dp[n - 1][2001] << '\n';
        return;
    }
}
int main() {
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    cin.tie(0), cout.tie(0)->sync_with_stdio(0);
    int T = 0;
    cin >> T;
    for (int i = 1; i <= 2000; i++) dp[0][i] = -1;
    for (int i = 1; i <= T; i++) work();
    return 0;
}
